class Solution {
    std::string expend(const std::string& s) {
        std::string res = "@#";
        for (int i = 0; i < s.size(); i++) res += s[i], res += '#';
        res += '%';
        return res;
    }
    std::vector<int> Manacher(const std::string &s){
        auto t=expend(s);
        std::vector<int>p(t.size());
        for(int i=1,r=0,c=0;i<t.size()-1;i++){
            p[i]=(r>i?std::min(p[2*c-i],r-i):1);
            while(t[i-p[i]]==t[i+p[i]])p[i]++;
            if(i+p[i]>r){
                r=i+p[i],c=i;
            }
        }
        return p;
    }

public:
    string shortestPalindrome(string s) {
        auto p=Manacher(s);
        //start=(i-p[i])/2
        auto get_start=[&](int idx)->int{
            return (idx-p[idx])/2;
        };

        int idx=0,len=0;;
        for(int i=1;i<p.size()-1;i++){
            if(get_start(i)==0)idx=i,len=p[i]-1;
        }
        auto sub=s.substr(len);
        std::reverse(sub.begin(),sub.end());
        return sub+s;
    }
};